package com.mlamp;

public class 布隆过滤器 {

    //1亿个网页的URL。我们会用什么样的数据结构呢。
    //可能是散列表，平衡二叉树或者跳表
    // 散列其实就是数组，借助hash函数，根据输入参数的特性返回一个数组的index，我们直接去这个index上查看即可。
    // 布隆过滤器只能判断给定的输入参数是否不存在，如果判定结果是存在，则可能存在，因为可能其他的输入跟当前的输入存在hash冲突。也就是说
    // 布隆过滤器存在一定的误判率，如何降低误判呢？
    // 一个是布隆过滤器的 size，还有一个就是哈希函数。
    // 正如散列表，有一个装填因子来保证实际的数据使用空间低于总空间，这样的话才能使得冲突尽可能的少。
    // 当然布隆过滤器是基于位图的，其占用的空间相比于散列表还是小了很多，一般实际空间和总空间 1:10 其实都不为过，这个比例绝大多数散列表是做不到的，特别是对于海量存储来说。因此这也就保证布隆过滤器的冲突发生几率要比散列表更加的小。
    // 另外一个影响冲突的因素是哈希函数，其实仅仅通过一个哈希函数来判断的话误判率确实会有点高，我们可以用多个哈希函数判断，这就好像有了多层保障，你必须保证满足条件1，条件2，条件3，…，才能被判定是 true，虽然说略微增加了时间的消耗，但是这些消耗往往都是常数级别的，误判率得到了有效的降低。
    // 增加布隆过滤器的大小，增加判断的哈希函数能够有效的降低误判率。

    // 应用场景，只要近似解的场景。不需要特别大的存储空间就可以让计算机去做几乎正确的事情，这也是其他的传统数据结构所不能达到的。


}
